import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class PopulatingNextRightPointersInEachNode {
    public Node connect(Node root) {
        if (root==null)
            return root;
        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(root);
        while (!queue.isEmpty()){
            List<Node> temp_list = new ArrayList<Node>();
            int len = queue.size();
            for(int i=0;i<len;i++){
                Node temp = queue.poll();
                temp_list.add(temp);
                if (temp.left!=null){
                    queue.add(temp.left);
                }
                if (temp.right!=null){
                    queue.add(temp.right);
                }

            }
            if (temp_list.size()!=0){
                for (int i=0;i<temp_list.size()-1;i++){
                    temp_list.get(i).next = temp_list.get(i+1);
                }
                temp_list.get(temp_list.size()-1).next = null;
            }
        }
        return root;

    }

}
